package pers.vic.basics.leetcode;

/**
 * @author Vic.xu
 * @description:44. 通配符匹配  动态规划
 * <p>
 * 给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
 * '?' 可以匹配任何单个字符。
 * '*' 可以匹配任意字符串（包括空字符串）。
 * 两个字符串完全匹配才算匹配成功。
 * <p>
 * s 可能为空，且只包含从 a-z 的小写字母。
 * p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。
 * @date: 2020/11/5  9:57
 * @see J0010_H_IsMatch_ 10. 正则表达式匹配 和第10题是一样类型，但是更简单一点
 */
public class J0044_H_IsMatch {
    /**
     * <p>
     * 2020年11月3日的时候刚接触动态规划  这一题我没写出来，
     * 现在是2020年12月8日，已经刷题一段时间，并且已经做过一些简单的动态规划，再次尝试写这一道题试试：
     * 动态规划三步走：
     * 1. 状态记录数组 dp[i+1][j+1] 字符串[0,i] 和字符模式[0,j]的匹配情况
     * 2.初始状态： [0][0] 空和空是匹配的  第一行 和第一列 的匹配需要额外的初始化
     * 3. 状态转移：
     * a.字符串和字符串不匹配 则false,匹配则是true 则看上一个位置[i-1][j-1]
     * b.字符串和? 是匹配的  则看上一个位置是否匹配[i-1][j-1]
     * c.字符串和*是匹配的，且可长可短，则
     * c1.当前* 没有匹配任何一个字符串()：[i][j-1]
     * c2 当前*匹配当前字符，类似？ 则：[i-1][j-1]
     * c3. 当前*匹配当前字符且继续往前匹配，则[i-1][j]
     * </p>
     */
    public static boolean isMatch(String s, String p) {
        int l1 = s.length();
        int l2 = p.length();
        // 字符串[0,i] 和字符模式[0,j]的匹配情况
        boolean[][] dp = new boolean[l1 + 1][l2 + 1];
        dp[0][0] = true;
        //空和字符模式的匹配情况
        for (int i = 1; i <= l2; i++) {
            if ('*' == p.charAt(i - 1)) {
                dp[0][i] = dp[0][i - 1];
            }
        }

        for (int i = 1; i <= l1; i++) {
            char c1 = s.charAt(i - 1);
            for (int j = 1; j <= l2; j++) {
                char c2 = p.charAt(j - 1);
                if ('?' == c2 || c1 == c2) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if ('*' == c2) {
                    dp[i][j] = dp[i - 1][j - 1] || dp[i][j - 1] || dp[i - 1][j];
                }

            }
        }

        return dp[l1][l2];
    }

    public static boolean isMatch2(String s, String p) {
        boolean table[][] = new boolean[s.length() + 1][p.length() + 1];

        table[0][0] = true;

        for (int col = 1; col < table[0].length; col++) {
            if (p.charAt(col - 1) == '*') {
                table[0][col] = table[0][col - 1];
            }
        }

        for (int row = 1; row < table.length; row++) {
            char ch1 = s.charAt(row - 1);
            for (int col = 1; col < table[row].length; col++) {
                char ch2 = p.charAt(col - 1);
                if (ch1 == ch2 || ch2 == '?') {
                    table[row][col] = table[row - 1][col - 1];
                } else if (ch2 == '*') {
                    table[row][col] = table[row][col - 1] || table[row - 1][col];
                }
            }
        }

        boolean[] lastRow = table[table.length - 1];
        return lastRow[lastRow.length - 1];


    }


    public static void main(String[] args) {
        //false
        System.out.println(isMatch("aa", "a"));
        //true
        System.out.println(isMatch("aa", "*"));
        //false
        System.out.println(isMatch("cb", "?a"));
        //true
        System.out.println(isMatch("adceb", "*a*b"));
        //false
        System.out.println(isMatch("acdcb", "a*c?b"));
        //true
        System.out.println(isMatch("abcabczzzde", "*abc???de*"));
        System.out.println("++++++++++++++");
        //false
        System.out.println(isMatch2("aa", "a"));
        //true
        System.out.println(isMatch2("aa", "*"));
        //false
        System.out.println(isMatch2("cb", "?a"));
        //true
        System.out.println(isMatch2("adceb", "*a*b"));
        //false
        System.out.println(isMatch2("acdcb", "a*c?b"));
        //true
        System.out.println(isMatch2("abcabczzzde", "*abc???de*"));
    }
}
